package day37_438;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * @ClassName Solution
 * @Description 哈希表+滑动窗口
 * @Author clockTown
 * @Date 2021/6/15 19:43
 * @Version 1.0
 */
public class Solution {
    public static List<Integer> findAnagrams(String s, String p) {
        //获取用于对比的字母异位词 hash 表
        HashMap<Character, Integer> map = getMap(p);
        //初始化结果集
        List<Integer> res = new ArrayList<>();
        //初始化滑动窗口
        HashMap<Character, Integer> window = new HashMap<>();
        if (s.length() < p.length()) {
            return null;
        }
        int r = 0, l = 0;

        //获取第一个窗口
        for (; r < p.length(); r++) {
            window.put(s.charAt(r), window.getOrDefault(s.charAt(r), 0) + 1);
        }
        if (window.equals(map)) {
            res.add(l);
        }
        //开始滑动
        while (r < s.length()) {
            //弹出左边的
            if (window.get(s.charAt(l)) <= 1) {
                window.remove(s.charAt(l));
            } else {
                window.replace(s.charAt(l), window.get(s.charAt(l)) - 1);
            }
            l++;
            //添加右边的
            window.put(s.charAt(r), window.getOrDefault(s.charAt(r), 0) + 1);
            if (window.equals(map)) {
                res.add(l);
            }
            r++;

        }
        return res;
    }

    private static HashMap<Character, Integer> getMap(String p) {
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < p.length(); i++) {
            map.put(p.charAt(i), map.getOrDefault(p.charAt(i), 0) + 1);
        }
        return map;
    }
}
